package com.cqs.leetcode.math;

import com.cqs.leetcode.TestCaseUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MaximumProductSubarray152 {


    static class Solution {
        public int maxProduct(int[] nums) {
            int max = Integer.MIN_VALUE, imax = 1, imin = 1;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] < 0) {
                    int tmp = imax;
                    imax = imin;
                    imin = tmp;
                }
                imax = Math.max(imax * nums[i], nums[i]);
                imin = Math.min(imin * nums[i], nums[i]);
                max = Math.max(max, imax);
            }
            return max;
        }
    }

    static class Solution1 {
        /***
         * 溢出case
         * [500, 20, -2, 100, 20, -2, -3, 9]
         * @param nums
         * @return
         */
        public int maxProduct(int[] nums) {
            long max = Integer.MIN_VALUE;
            long sum = 1;
            for (int num : nums) {
                if (num == 0) {
                    max = Math.max(max, 0);
                    sum = 1;
                    continue;
                }
                sum *= num;
                max = Math.max(sum, max);
            }
            sum = 1;
            for (int i = nums.length - 1; i >= 0; i--) {
                int num = nums[i];
                if (num == 0) {
                    max = Math.max(max, 0);
                    sum = 1;
                    continue;
                }
                sum *= num;
                max = Math.max(sum, max);
            }
            return (int) max;
        }

        public static void main(String[] args) {
            Solution solution = new Solution();
            Solution1 solution1 = new Solution1();
            List<int[]> testCase = new ArrayList<>();
            testCase.add(new int[]{-5, -8, -10, 0, -3, -4});
//            testCase.add(new int[]{-5, 0, -3, 0, -3});
//            testCase.add(new int[]{-5, -3, 0, -3});
//            testCase.add(new int[]{-5, -3, 0, -3, -9});
//            testCase.add(new int[]{-5, 1, 3, 100, 0, -3, -9});
//            testCase.add(new int[]{5, 20, -2, 100, 20, -3, -9});
//            testCase.add(new int[]{500, 20, -2, 100, 20, -3, -9});
//            testCase.add(new int[]{500, 20, -2, 100, 20, -2, -3, -9});
//            testCase.add(new int[]{500, 20, -2, 100, 20, -2, -3, 9});
//            System.out.println(Arrays.stream(new int[]{500, 20, -2, 100, 20, -2, -3, 9}).sum());
//            testCase.add(new int[]{-1, -2, -9, -6});
            testCase.forEach(arr -> {
                int max = solution.maxProduct(arr);
                System.out.println(TestCaseUtils.arrFormat(arr) + "\t max:" + max);
            });
        }
    }

    static class Solution2 {
        /***
         * 溢出case
         * [500, 20, -2, 100, 20, -2, -3, 9]
         * @param nums
         * @return
         */
        public int maxProduct(int[] nums) {
            if (nums == null || nums.length < 1) return 0;
            long max = nums[0];
            //cmax 并不是整个数组当前的最大值，
            // 而是以0进行分割，包含nums[i]子数组的最大值,若nums[i]=0,那么该子数组可视为只包含0
            int cmax = 1;
            int cmin = 1;
            for (int num : nums) {
                //若num >= 0 ,子数组的最大值是前最大值*num,
                //若num <0 ,子树组的最大值是之前最小值*num,
                if (num < 0) {
                    int t = cmax;
                    cmax = cmin;
                    cmin = t;
                }
                cmax = Math.max(cmax * num, num);
                cmin = Math.min(cmin * num, num);
                max = Math.max(max, cmax);
            }
            return (int) max;
        }

        public static void main(String[] args) {
            Solution solution = new Solution();
            Solution1 solution1 = new Solution1();
            Solution2 solution2 = new Solution2();
            List<int[]> testCase = new ArrayList<>();
            testCase.add(new int[]{0, 2});
            testCase.add(new int[]{-5, -8, -10, 0, -3, -4});
            testCase.add(new int[]{-5, 0, -3, 0, -3});
            testCase.add(new int[]{-5, -3, 0, -3});
            testCase.add(new int[]{-5, -3, 0, -3, -9});
            testCase.add(new int[]{-5, 1, 3, 100, 0, -3, -9});
            testCase.add(new int[]{5, 20, -2, 100, 20, -3, -9});
            testCase.add(new int[]{500, 20, -2, 100, 20, -3, -9});
            testCase.add(new int[]{500, 20, -2, 100, 20, -2, -3, -9});
            testCase.add(new int[]{500, 20, -2, 100, 20, -2, -3, 9});
            System.out.println("求和：" + Arrays.stream(new int[]{500, 20, -2, 100, 20, -2, -3, -9}).reduce(1, (left, right) -> left * right));
            testCase.add(new int[]{-1, -2, -9, -6});
            testCase.forEach(arr -> {
                int max = solution2.maxProduct(arr);
                System.out.println(TestCaseUtils.arrFormat(arr) + "\t max:" + max + "\t" + solution.maxProduct(arr));
            });
        }
    }
}